1950E - Nearly Shortest Repeating Substring - CodeForces Solution

def subst(s, st, ed):
    result = []
    for i in range(st, ed):
        result.append(s[i])
    return ''.join(result)

for _ in range(int(input())):
    n = int(input())
    s = input().strip()
    f = 0
    
        for i in range(1, n // 2 + 1):
        if n % i == 0:
            dic = {}
            dicsz = 0
            for j in range(0, n, i):
                dd = subst(s, j, j + i)
                if dd not in dic:
                    dic[dd] = 1
                    dicsz += 1
                else:
                    dic[dd] += 1
            if dicsz == 1:
                for _, dj in dic.items():
                    if i * dj == n and f <= 1:
                        print(i)
                        f = 1
                        break
            if dicsz == 2:
                x = list(dic.keys())
                c = sum(x[0][comp] != x[1][comp] for comp in range(i))
                for _, j in dic.items():
                    if i * (j + 1) == n and c <= 1:
                        print(i)
                        f = 1
                        break
            if f == 1:
                break
                
    if f == 0:
        print(n)